package com.company;

/**
 * Created by dwk on 18-11-22.
 */
public class 快速排序 {
    public static void sort(int[] a, int low, int high) {

        if (low > high) {
            return;
        }
        int start = low;
        int end = high;
        int key = a[start];

        while (start < end) {
            while (start < end && a[end] > key) {
                end--;
            }
            a[start] = a[end];
            while (start < end && a[start] < key) {
                start++;
            }
            a[end] = a[start];
        }
        a[start] = key;
        System.out.println(key);
        sort(a, low, start - 1);
        sort(a, start + 1, high);
    }







    static void print(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void sort2(int arr[], int low, int high) {
        if (low > high) {
            return;
        }
        int first = low;
        int last = high;
        int key = arr[low];

        while (first < last) {
            while (first < last && arr[last] >= key) {
                last--;
            }
            if (first < last) {
                int temp = arr[last];
                arr[last] = arr[first];
                arr[first] = temp;
                first++;
            }

            while (first < last && arr[first] <= key) {
                first++;
            }

            if (first < last) {
                int temp = arr[last];
                arr[last] = arr[first];
                arr[first] = temp;
                last--;
            }
        }
        System.out.print("first=" + (first + 1) + "last=" + (last + 1) + "key=" + key + "\n");
        sort(arr, low, first - 1);
        sort(arr, first + 1, high);
    }






















    public static void quickSort(int[] a, int start, int end) {
        //flag表示快排时游标移动的方向；若为false表“左->右”，若为true表“右->左”；
        boolean flag = true;
        int i = start;
        int j = end;

        if (i > j) { // 判断是否到中间了,这也是递归的结束条件；
            return;
        }

        while (i < j) {
            //若是前面的数大于后面的数，那么两个数就交换；
            if (a[i] > a[j]) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
                //只有经过数的交换后，才能把游标移动的方向改变；
                flag = !flag;
            }
            //根据flag的值决定下标移动，还是上标移动 ，使游标更改走下一个数据；
            if (flag)
                j--;
            else
                i++;
        }
        //通过递归实现整体的快速排序；
        quickSort(a, start, i - 1);
        quickSort(a, j + 1, end);

    }
}
